iT邦幫忙

2024 iThome 鐵人賽

DAY 27
0
Python

30天Python學習之旅系列 第 27

Day 27 : 簡單實作 ( 迷宮問題 )

  • 分享至 

  • xImage
  •  

今天是 Python 學習的第 26 天,實作的難度會稍微提升,會使用遞迴概念實作一個解決迷宮問題的演算法。迷宮問題是經典的回溯法應用,需要找到一條從起點到終點的路徑,且只能在允許的路徑 (0 代表之)上行走,不能穿越障礙物 (1 代表之)。這個問題的解法可以透過回溯法來實現,回溯法是一種嘗試錯誤的策略,當發現當前路徑不可行時,會回到之前的步驟,嘗試其他可能的方向。

步驟:

  1. 定義迷宮地圖
    使用一個二維列表表示迷宮,0 代表可以通行的路徑,1 代表障礙物。起點預設在左上角 (0, 0),終點在右下角 (4, 4)。
    https://ithelp.ithome.com.tw/upload/images/20241010/20169078TFVnwD2hhx.png

  2. 建立解決方案框架
    建立一個遞迴函數來嘗試找到解決迷宮的路徑。solve_maze 函數會檢查當前位置是否有效,並使用遞迴探索所有可能的路徑,直到找到終點或無法前進為止。每次遞迴呼叫會嘗試向下、右、上、左方向移動。
    https://ithelp.ithome.com.tw/upload/images/20241010/20169078PNl4qQAWT7.png
    https://ithelp.ithome.com.tw/upload/images/20241010/20169078PxjF2LvKSP.png

  3. 呼叫函數進行求解
    呼叫 solve_maze 函數,並檢查是否找到可行路徑,如果找到路徑,會輸出該路徑,若沒辦法找到就會提示無法找到路徑。
    https://ithelp.ithome.com.tw/upload/images/20241010/201690785GIr7vnA78.png

輸出結果:

找到路徑: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]


上一篇
Day 26 : 簡單實作 ( 凱撒加密法 )
下一篇
Day 28 : 簡單實作 ( 圓周率的蒙地卡羅模擬法 )
系列文
30天Python學習之旅30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言